1. Field of Invention
Embodiments of the present invention generally relate to building a cell and portal graph corresponding to two-dimensional (2D) or three-dimensional (3D) graphics data. More specifically, embodiments of the invention relate to techniques for generating a data structure that encodes conservative occlusion information for the graphics data. i.e., the cell and portal graph.
2. Description of the Related Art
Rendering is the process of generating an image from a model in a database that contains information concerning the scene such as object definitions, lighting, texture and possibly other properties. This information is passed along to a computer program which assembles this information into a raster graphics image. The more complex a scene, the more resource intensive rendering operations become. To offload some of this computational load, Graphic Processing Units (GPU) were developed to assist the CPU in performing the complex rendering operations present in graphic intensive programs such as computer gaming. The two techniques used for three dimensional (3D) graphic rendering are pre-rendering and real-time.
Real-time rendering of computer graphics has at least three performance goals: to generate more frames per second, at a higher resolution, and to display more objects in a scene. Rendering is a resource intensive operation and performance can be optimized by rendering the least amount of objects possible. This is done by rendering only those objects which are necessary to be visible in a scene. Culling is the process of removing items from a group based on specific criteria. In computer graphics, a selection of scenes that are not visible from a user perspective is removed from the computer rendering process through the method of culling. Computer programmer's use culling to determine what parts of a rendering operation can be skipped to enhance performance. The rendering of geometry elements can therefore be culled by determining the visibility of those elements within a view frustum.
Some techniques of culling include: Back Face Culling where Faces that face away from the camera are not drawn; View frustum Culling where objects are culled if they are outside the view frustum; Portal Culling that divides the scene into cells with portals between them for rendering; Detail Culling that decreases the amount of details based on distance; and Occlusion Culling where geometry that is occluded by other geometry is not rendered. All these techniques can be costly to the Graphics Processing Unit (GPU). Also, culling techniques require a great deal of manual labor for a programmer to place culling tiles in the scene in order for objects to be culled. Another solution is to use a Z-buffer and sort graphics geometry in a front to back order. Although only the object closest to the user is rendered in Z-buffering, all objects still go through the pipeline.